0920. 播放列表的数量【困难】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 解法 1

1. 📝 题目描述

• leetcode

你的音乐播放器里有 n 首不同的歌，在旅途中，你计划听 goal 首歌（不一定不同，即，允许歌曲重复）。你将会按如下规则创建播放列表：

• 每首歌 至少播放一次。
• 一首歌只有在其他 k 首歌播放完之后才能再次播放。

给你 n、goal 和 k，返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回对 10^9 + 7 取余 的结果。

---

示例 1：

输入：n = 3, goal = 3, k = 1
输出：6
解释：有 6 种可能的播放列表。[1, 2, 3]，[1, 3, 2]，[2, 1, 3]，[2, 3, 1]，[3, 1, 2]，[3, 2, 1]。

示例 2：

输入：n = 2, goal = 3, k = 0
输出：6
解释：有 6 种可能的播放列表。[1, 1, 2]，[1, 2, 1]，[2, 1, 1]，[2, 2, 1]，[2, 1, 2]，[1, 2, 2]。

示例 3：

输入：n = 2, goal = 3, k = 1
输出：2
解释：有 2 种可能的播放列表。[1, 2, 1]，[2, 1, 2]。

---

提示：

• 0 <= k < n <= goal <= 100

2. 🎯 s.1 - 解法 1

js

// todo

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$